package com.cdream.basic.algorithm.leetcode.tree;

public class Question117 {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        if (root.left==null && root.right==null){
            return root;
        }
        if (root.left != null) {
            if (root.right != null) {
                root.left.next = root.right;
            } else {
                Node temp = root;
                while (temp.next != null) {
                    if (temp.next.left != null) {
                        root.left.next = temp.next.left;
                        break;
                    }
                    if (temp.next.right != null) {
                        root.left.next = temp.next.right;
                        break;
                    }
                    temp = temp.next;
                }
            }

        }

        if (root.right != null) {
            Node temp = root;
            while (temp.next != null) {
                if (temp.next.left != null) {
                    root.right.next = temp.next.left;
                    break;
                }
                if (temp.next.right != null) {
                    root.right.next = temp.next.right;
                    break;
                }
                temp = temp.next;
            }
        }
        connect(root.right);
        connect(root.left);
        return root;
    }
}
